package 每日一题;

import com.alibaba.fastjson.JSON;
import 我的JDK基础数据结构.LinkedList.LinkedList;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class No131分割回文串 {

    /**
     * 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
     *
     * 返回 s 所有可能的分割方案。
     *
     * 示例:
     *
     * 输入: "aab"
     * 输出:
     * [
     *   ["aa","b"],
     *   ["a","a","b"]
     * ]
     */

    private List<List<String>> lists=new ArrayList<>();
    private char[] arr;
    private boolean[][] dp;

    public List<List<String>> partition(String s) {
        this.arr=s.toCharArray();
        initValid();
        dfs(0,new ArrayDeque<>());
        return lists;
    }

    private void dfs(int index,ArrayDeque<String> path){
        if(index==arr.length){
            lists.add(new ArrayList<>(path));
            return;
        }

        for (int i = index; i < arr.length; i++) {
            //验证 [left,right]是否为回文字符串
            if(!isValid(index,i)){
                continue;
            }
            path.addLast(new String(arr,index,i-index+1));//最后一个参数是count
            dfs(i+1,path);
            path.removeLast();
        }

    }

    private void initValid(){
        dp=new boolean[arr.length][arr.length];
        for (int i = arr.length-1; i >= 0; i--) {
            dp[i][i]=true;
            for (int j = i+1; j < arr.length ; j++) {
                if(arr[i]==arr[j]&&((j-i)<=2||dp[i+1][j-1])){
                    dp[i][j]=true;
                }
            }
        }
    }

    private boolean isValid(int left,int right){
        return dp[left][right];
    }

    public static void main(String[] args) {
        No131分割回文串 n=new No131分割回文串();
        List<List<String>> result = n.partition("aabb");
        System.out.println(JSON.toJSONString(result));
    }

}
